A digital multiplier embodying the invention is essentially a Booth multiplier. To understand the invention, it is necessary to have some understanding of the mode of operation of a Booth multiplier. Booth multiplication is discussed in the book Computer Arithmetic by Kai Hwang (Wiley, 1979). The method described in the detailed description is the so-called modified Booth encoding, but it will be called Booth encoding for brevity.
A primary goal of the invention is to have standardized layout procedures for integrated-circuit digital multipliers that accommodate their design by silicon compiler methods. It is desirable for "custom" integrated circuit design purposes to have an array multiplier in which a close-packed array by row and by column of multiplier cells can be extended in both the row and column dimensions to accommodate multiplier and multiplicand signals having words of any specified bit-width. Further aspects of the invention extend to "semi-custom" design procedures in which standardized "chunks" or close-packed arrays of multiplier cells by row and by column are disposed on a monolithic integrated circuit and are interconnected by discretionary top-level metallization to form digital multipliers with multiplier and multiplicand signals having respective words of differing specified bit-widths. A basic problem encountered in the design of multipliers that can accomodate multiplier and multiplicand signals of differing specified bit-widths is how best to combine partial product terms, in order to avoid concatenating long ripple carry times, which would slow the generation of digital products. The use of Booth encoding is known to be helpful in this regard since it halves the number of partial products that have to be combined.
Where the bit-width of the multiplier words is always the same, a procedure that has been generally used in the prior art to reduce the time required for combining partial products is to sum the partial products with a tree of adders rather than a chain of adders. This speed-up procedure is not used in digital multipliers constructed in accordance with the invention, because the tree connection of adders is not susceptible readily (if at all) to the regular tessellation and interconnection procedures preferred by the silicon compiler.